// https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
#include <vector>
#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
		if(n == 0){
			return head;
		}
		ListNode * pos = nullptr;
		ListNode * index = head;
		while(index){
			index = index->next;
			n--;
			if(pos){
				pos = pos->next;
			}
			if(n == -1){
				pos = head;
			}
		}
		if(n <= 0){
			if(pos){
				auto next = pos->next;
				pos->next = next->next;
				next->next = nullptr;
			}else{
				head = head->next;
			}
		}
		
		return head;
    }
	
	ListNode * init(vector<int> & elements){
		int len = elements.size();
		if(len == 0){
			return nullptr;
		}
		ListNode * head = new ListNode;
		head->val = elements[0];
		head->next = nullptr;
		ListNode * pos = head;
		for(int i = 1; i < len; i++){
			ListNode * tmp = new ListNode;
			tmp->val = elements[i];
			tmp->next = nullptr;
			pos->next = tmp;
			pos = pos->next;
		}
		return head;
	}
	
	void showListNode(ListNode * listNode){
		while(listNode){
			cout << listNode->val << ", ";
			listNode = listNode->next;
		}
		cout << endl;
	}
};

int main(){
	vector<int> nums = {1};
	int n = 1;
	Solution so;
	ListNode * list = so.init(nums);
	so.showListNode(list);
	ListNode * list1 = so.removeNthFromEnd(list, 1);
	so.showListNode(list1);
	
	return 0;
}